package bill.study.algorithms.arraysStrings;

public class MaxSubArray {
	
	static	int  maxSubArray(int [] array){
		// safeguard the params
		if(array == null){
			//
		}
		
		if(array.length ==0){
			//
		}
		
		int maxSoFar = 0;
		int maxEndingHere = 0;
		for(int i = 0; i < array. length; i ++){
			maxEndingHere = Math.max(0, maxEndingHere + array[i]);
			maxSoFar = Math.max(maxSoFar, maxEndingHere);
		}
		return maxSoFar;
		
	}
	public static void main(String [] args){
		int [] arr1 = new int[]{10,-11, 1,2,3,-1,-2};
		int [] arr2 = new int[]{10,-9, 10, -1,-2,-3};
		int [] arr3 = new int[]{10,-9,10,-12, 1,2,3,4,5};
		
		System.out.println("max of arr1 by maxsubsum: " + maxsubsum(arr1));
		System.out.println("max of arr2 by maxsubsum: " + maxsubsum(arr2));
		System.out.println("max of arr3 by maxsubsum: " + maxsubsum(arr3));
		System.out.println("Hello");
		
		System.out.println("max of arr1 by maxSubArray: " + maxSubArray(arr1,7));
		System.out.println("max of arr2 by maxSubArray: " + maxSubArray(arr2,6));
		System.out.println("max of arr3 by maxSubArray: " + maxSubArray(arr3,9));
		
System.out.println("Hello");
		
		System.out.println("max of arr1 by maxSubArray1: " + maxSubArray(arr1));
		System.out.println("max of arr2 by maxSubArray1: " + maxSubArray(arr2));
		System.out.println("max of arr3 by maxSubArray1: " + maxSubArray(arr3));
		
	}
	
	static int maxsubsum(int [] array){
		int max = 0;
		int start = -1;
		int end = -1;
		int i = 0;
		int tempEnd = 0;
		while ( i < array.length && tempEnd < array.length){
			int running = 0;
			tempEnd = i;
			while(tempEnd < array.length){
				running += array[tempEnd];
				if(running > max){
					max = running;
					start = i;
					end = tempEnd;
				}
				
				if (running > 0){
					tempEnd ++;
				}
				else{
					i = tempEnd +1;
					break;
				}
			}
		}
		return max;
	}

	
	//@TODO  make sure it immutable
	private final static  class Result{
		int starting;
		int ending;
		int endingMax;
		int max;
	private	Result(int s, int e, int endingMax,  int max){
			this.starting =s;
			this.ending = e;
			this.endingMax = endingMax;
			this.max = max;
		}
	
	public String toString(){
		return "[max :" + this.max + " ; starting: " + this.starting+ " ; ending: "+ this.ending +"]";
	}
	}
	
	static Result maxSubArray(int [] array,  int n){
		
		if(n ==1){
			// base step
			return new Result(0, 0,array[0], array[0]);
		}else{
			Result res=    maxSubArray(array, n-1 );
			if (res.ending == n-1){
				return new Result (res.starting, res.ending, Math.max(res.max, res.max+array[n-1]),Math.max(res.max, res.max+array[n-1]));
			}else{
				int tempEndingMax =Math.max(res.endingMax,res.endingMax + array[n-1]);
				int tempMax = Math.max(res.max, tempEndingMax);
				return new Result(res.starting, n-1, tempEndingMax,tempMax);
			}
		}
	}

}
